import java.util.Arrays;

public class CoinChange {
    // https://leetcode.cn/problems/coin-change/submissions/431413451/
    class Solution {
        public int coinChange(int[] coins, int amount) {

            int [] dp = new int[amount+1];

            Arrays.fill(dp,0x3f3f3f3f);
            dp[0] = 0;
            for(int i = 1 ; i <= amount ; i ++)
            {
                for(int j = 0 ; j < coins.length ; j ++)
                {
                    if(i >= coins[j] && dp[i-coins[j]] != 0x3f3f3f3f)
                    {
                        dp[i] = Math.min(dp[i],dp[i-coins[j]] + 1);
                    }

                }
            }
            if(dp[amount] >= 0x3f3f3f3f) return -1;
            return dp[amount];

        }
    }
}
